<!DOCTYPE html>



  


<html class="theme-next muse use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/yangshucheng2020/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/yangshucheng2020/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/yangshucheng2020/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/yangshucheng2020/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/yangshucheng2020/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/yangshucheng2020/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/yangshucheng2020/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="算法,回溯法," />










<meta name="description" content="循环赛制这种解法是把求解 2^k^ 个选手的比赛日程问题划分为 2^1^ , 2^2^ ，……，2^k^  个选手的比赛日程问题。也就是说，要求 2^k^个选手的比赛日程，就要分为两部分，分别求出 2^(k-1)^ 个选手的比赛日程，然后再进行合并。当然，这种解法只能求选手个数是2的次幂的情况。 在每次迭代求解的过程中，可以看作4部分： 1）求左上角子表：左上角子表是前 2^(k-1)^ 个选手的">
<meta property="og:type" content="article">
<meta property="og:title" content="回溯法">
<meta property="og:url" content="http://yangshucheng2020.gitee.io/yangshucheng2020/2020/03/27/%E5%9B%9E%E6%BA%AF%E6%B3%95/index.html">
<meta property="og:site_name" content="羊书change">
<meta property="og:description" content="循环赛制这种解法是把求解 2^k^ 个选手的比赛日程问题划分为 2^1^ , 2^2^ ，……，2^k^  个选手的比赛日程问题。也就是说，要求 2^k^个选手的比赛日程，就要分为两部分，分别求出 2^(k-1)^ 个选手的比赛日程，然后再进行合并。当然，这种解法只能求选手个数是2的次幂的情况。 在每次迭代求解的过程中，可以看作4部分： 1）求左上角子表：左上角子表是前 2^(k-1)^ 个选手的">
<meta property="og:image" content="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200325133716157.png">
<meta property="og:image" content="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200325135817004.png">
<meta property="og:image" content="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200325135653425.png">
<meta property="og:image" content="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200325133826887.png">
<meta property="og:image" content="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200326170059426.png">
<meta property="og:image" content="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200326170152534.png">
<meta property="og:image" content="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200326170523901.png">
<meta property="og:image" content="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200326145529471.png">
<meta property="article:published_time" content="2020-03-27T02:39:10.718Z">
<meta property="article:modified_time" content="2020-03-27T04:34:25.106Z">
<meta property="article:author" content="羊书change">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="回溯法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200325133716157.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/yangshucheng2020/',
    scheme: 'Muse',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yangshucheng2020.gitee.io/yangshucheng2020/2020/03/27/回溯法/"/>





  <title>回溯法 | 羊书change</title>
  








<meta name="generator" content="Hexo 4.2.0"></head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/yangshucheng2020/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">羊书change</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/yangshucheng2020/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/yangshucheng2020/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/yangshucheng2020/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/yangshucheng2020/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yangshucheng2020.gitee.io/yangshucheng2020/yangshucheng2020/2020/03/27/%E5%9B%9E%E6%BA%AF%E6%B3%95/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="羊书change">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/海绵jojo.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="羊书change">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">回溯法</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2020-03-27T10:39:10+08:00">
                2020-03-27
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/yangshucheng2020/categories/%E5%AD%A6%E4%B9%A0/" itemprop="url" rel="index">
                    <span itemprop="name">学习</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <h2 id="循环赛制"><a href="#循环赛制" class="headerlink" title="循环赛制"></a>循环赛制</h2><p>这种解法是把求解 2^k^ 个选手的比赛日程问题划分为 2^1^ , 2^2^ ，……，2^k^  个选手的比赛日程问题。也就是说，要求 2^k^个选手的比赛日程，就要分为两部分，分别求出 2^(k-1)^ 个选手的比赛日程，然后再进行合并。当然，这种解法只能求选手个数是2的次幂的情况。</p>
<p>在每次迭代求解的过程中，可以看作4部分：</p>
<p>1）求左上角子表：左上角子表是前 2^(k-1)^ 个选手的比赛前半程的比赛日程。</p>
<p>2）求左下角子表：左下角子表是剩余的 2^(k-1)^ 个选手的比赛前半程比赛日程。这个子表和左上角子表的对应关系式，对应元素等于左上角子表对应元素加 2^(k-1)^ 。</p>
<p>3）求右上角子表：等于左下角子表的对应元素。</p>
<p>4）求右下角子表：等于左上角子表的对应元素。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">GameTable</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; &amp;vec)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(vec.<span class="built_in">size</span>() == <span class="number">0</span>)&#123;<span class="comment">//如果向量数组大小为0，返回</span></span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;<span class="comment">//s为vec的行大小</span></span><br><span class="line">    <span class="keyword">size_t</span> s = vec.<span class="built_in">size</span>();</span><br><span class="line">    <span class="keyword">int</span> k = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(s = s &gt;&gt; <span class="number">1</span>)&#123;</span><br><span class="line">        <span class="comment">//计算出2^k 中的k的大小</span></span><br><span class="line">        k++;</span><br><span class="line">        &#125;</span><br><span class="line">    <span class="comment">//初始化</span></span><br><span class="line">    vec[<span class="number">0</span>][<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">    vec[<span class="number">0</span>][<span class="number">1</span>] = <span class="number">2</span>;</span><br><span class="line">    vec[<span class="number">1</span>][<span class="number">0</span>] = <span class="number">2</span>;</span><br><span class="line">    vec[<span class="number">1</span>][<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">2</span>; i &lt;= k; i++)&#123;</span><br><span class="line">        <span class="keyword">int</span> length = <span class="number">0x1</span> &lt;&lt; i;<span class="comment">//length = 2^i,当前填写表格的长度</span></span><br><span class="line">        <span class="keyword">int</span> half = length &gt;&gt; <span class="number">1</span>;<span class="comment">//half = 2^(i-1)，长度的一半</span></span><br><span class="line">        <span class="comment">//左下角的子表中项为左上角子表对应项加half=2^(i-1)</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> row = <span class="number">0</span>; row &lt; half; row++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> col = <span class="number">0</span>; col &lt; half; col++)&#123;</span><br><span class="line">                vec[row + half][col] = vec[row][col] + half;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//右上角的子表 = 左下角子表</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> row = <span class="number">0</span>; row &lt; half; row++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> col = <span class="number">0</span>; col &lt; half; col++)&#123;</span><br><span class="line">                vec[row][col + half] = vec[row + half][col];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//右下角的子表 = 左上角子表</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> row = <span class="number">0</span>; row &lt; half; row++)&#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> col = <span class="number">0</span>; col &lt; half; col++)&#123;</span><br><span class="line">                vec[row + half][col + half] = vec[row][col];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">(<span class="keyword">void</span>)</span></span>&#123;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"共有2^k个选手参加比赛，输入k（k&gt;0）："</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="keyword">int</span> k;</span><br><span class="line">    <span class="keyword">do</span>&#123;</span><br><span class="line">        <span class="built_in">cin</span> &gt;&gt; k;</span><br><span class="line">    &#125;<span class="keyword">while</span>(k &lt; <span class="number">0</span> || k &gt; <span class="number">31</span>);</span><br><span class="line">    <span class="keyword">int</span> s = <span class="number">0x1</span> &lt;&lt; k;</span><br><span class="line">    <span class="function"><span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &gt; <span class="title">vec</span><span class="params">(s, <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;(s, <span class="number">0</span>))</span></span>;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; vec.<span class="built_in">size</span>() &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="comment">//一个二维int类型s*s个元素向量数组，且值均为0的vector容器vec</span></span><br><span class="line">    GameTable(vec);</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">size_t</span> i = <span class="number">0</span>; i &lt; vec.<span class="built_in">size</span>(); i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">size_t</span> j = <span class="number">0</span>; j &lt; vec[i].<span class="built_in">size</span>(); j++)&#123;</span><br><span class="line">            <span class="built_in">cout</span> &lt;&lt; vec[i][j] &lt;&lt; <span class="string">" "</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="装载问题"><a href="#装载问题" class="headerlink" title="装载问题"></a>装载问题</h2><p> <em>每组测试数据：第1行有2个整数c和n。C是轮船的载重量（0＜c＜30000），n是集装箱的个数（n≤20）。第2行有n个整数w1, w2, …, wn，分别表示n个集装箱的重量。</em></p>
<p> <em>输出</em></p>
<p> <em>对每个测试例，输出两行：第1行是装载到轮船的最大载重量，第2行是集装箱的编号。</em></p>
<p> <em>输入样例</em></p>
<p> <em>34 3</em></p>
<p> <em>21 10 5</em></p>
<p> <em>输出（考虑最大装载量的最优解）</em></p>
<p> <em>31（重量）</em></p>
<p> <em>1 2</em></p>
<p> <em>考虑最大装载件数的最优解</em></p>
<p> <em>2（件）</em></p>
<p> <em>5 10</em></p>
<h3 id="简单回溯法"><a href="#简单回溯法" class="headerlink" title="简单回溯法"></a>简单回溯法</h3><p>扫描当前w[k]箱子的重量，如果能放则放，接着递归，其他情况都是不放（包含放不下去和故意不放的情况）</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXN = <span class="number">1000</span>;</span><br><span class="line"><span class="keyword">int</span> w[MAXN];</span><br><span class="line"><span class="keyword">int</span> C,n,bestw = <span class="number">0</span>;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Contain</span><span class="params">(<span class="keyword">int</span> k,<span class="keyword">int</span> currentw)</span></span>&#123;<span class="comment">//选择第k件物品，当前最大值为MAX,可容纳最大总重量为weight</span></span><br><span class="line">    <span class="keyword">if</span> (k &gt;= n) &#123;</span><br><span class="line">        <span class="keyword">if</span> (bestw &lt; currentw ) &#123;</span><br><span class="line">            bestw = currentw;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (w[k] + currentw &lt;= C)<span class="comment">//不超重，可以选择第k个物品</span></span><br><span class="line">        Contain(k + <span class="number">1</span>,currentw + w[k]);</span><br><span class="line">    Contain(k + <span class="number">1</span>, currentw);<span class="comment">//不选择当前物品，直接扫描下一个物品</span></span><br><span class="line">    <span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"输入轮船载重量C,集装箱个数n,n个箱子的重量"</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">    <span class="built_in">cin</span> &gt;&gt; C &gt;&gt; n;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; ++i) &#123;</span><br><span class="line">        <span class="built_in">cin</span> &gt;&gt; w[i];</span><br><span class="line">    &#125;</span><br><span class="line">    Contain(<span class="number">0</span>, <span class="number">0</span>);</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; bestw;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="使用限界函数"><a href="#使用限界函数" class="headerlink" title="使用限界函数"></a>使用限界函数</h3><p>改进的回溯算法<br>利用限界函数其中， ow表示剩余货箱的总重量<br>剪枝<br>若 w[k] + currentw + ow  &lt;= bestw ，则停止搜索第 i 层及其下面的层，否则，继续搜索。其中，bestw 表示目前为止所得到的最佳重量</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXN = <span class="number">1000</span>;</span><br><span class="line"><span class="keyword">int</span> w[MAXN];</span><br><span class="line"><span class="keyword">int</span> C,n,sum = <span class="number">0</span>,bestw = <span class="number">0</span>;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Contain</span><span class="params">(<span class="keyword">int</span> k,<span class="keyword">int</span> currentw,<span class="keyword">int</span> ow)</span></span>&#123;</span><br><span class="line">    <span class="comment">//选择第k件物品，当前最大值为MAX,可容纳最大总重量为weight，剩余的货物质量为ow</span></span><br><span class="line">    <span class="keyword">if</span> (k &gt;= n) &#123;</span><br><span class="line">        <span class="keyword">if</span> (bestw &lt; currentw ) &#123;</span><br><span class="line">            bestw = currentw;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    ow -= w[k];</span><br><span class="line">    <span class="keyword">if</span> (w[k] + currentw + ow &lt;= bestw) &#123;</span><br><span class="line">        <span class="comment">//选择全部剩下的物品时不超过最大值，则不需搜索</span></span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (w[k] + currentw &lt;= C)</span><br><span class="line">        <span class="comment">//不超重，则可以选择第k个物品</span></span><br><span class="line">        Contain(k + <span class="number">1</span>,currentw + w[k],ow);</span><br><span class="line">    Contain(k + <span class="number">1</span>, currentw,ow);<span class="comment">//不选择当前物品，直接扫描下一个物品</span></span><br><span class="line">    <span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"输入轮船载重量C,集装箱个数n,n个箱子的重量"</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">    <span class="built_in">cin</span> &gt;&gt; C &gt;&gt; n;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; ++i) &#123;</span><br><span class="line">        <span class="built_in">cin</span> &gt;&gt; w[i];</span><br><span class="line">        sum += w[i];</span><br><span class="line">    &#125;</span><br><span class="line">    Contain(<span class="number">0</span>, <span class="number">0</span>,sum);</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; bestw;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="地图着色问题"><a href="#地图着色问题" class="headerlink" title="地图着色问题"></a>地图着色问题</h2><p>图的m-着色判定问题——给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?</p>
<p>图的m-着色优化问题——若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的最小色数m的问题称为m-着色优化问题。</p>
<p>回溯过程：</p>
<ol>
<li><p>填充该颜色</p>
</li>
<li><p>判断是否合法，合法则继续填充下一个</p>
</li>
<li><p>不合法则回溯：去掉颜色color[k] = 0，返回上一个点k–</p>
</li>
<li><p>如果找到其中一种方法则输出</p>
</li>
</ol>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="keyword">int</span> color[<span class="number">500</span>];<span class="comment">//存储填充颜色的具体方案，color[i]表示点i的颜色</span></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">ok</span><span class="params">(<span class="keyword">int</span> k,<span class="keyword">int</span> c[][<span class="number">100</span>])</span></span></span><br><span class="line"><span class="function"></span>&#123;<span class="comment">//判断顶点k相连的边与它颜色是否相同</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>;i &lt; k;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(c[k][i] == <span class="number">1</span> &amp;&amp; color[i] == color[k])</span><br><span class="line">        <span class="comment">//如果已经着色的k 与之相连的顶点和他同色，返回假</span></span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">graphColor</span><span class="params">(<span class="keyword">int</span> n,<span class="keyword">int</span> m,<span class="keyword">int</span> c[][<span class="number">100</span>])</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> cnt=<span class="number">0</span>;<span class="comment">//统计填色方案种类数量</span></span><br><span class="line">    <span class="built_in">memset</span>(color,<span class="number">0</span>,<span class="keyword">sizeof</span>(color));<span class="comment">//初始化</span></span><br><span class="line">    <span class="keyword">int</span> k=<span class="number">1</span>;<span class="comment">//从点k=1开始染色</span></span><br><span class="line">    <span class="keyword">while</span>(k&gt;=<span class="number">1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        color[k]+=<span class="number">1</span>;<span class="comment">///染第一种颜色</span></span><br><span class="line">        <span class="keyword">while</span>(color[k] &lt;= m)</span><br><span class="line">        &#123;<span class="comment">//当还可以填充颜色的时候</span></span><br><span class="line">            <span class="keyword">if</span>(ok(k,c))</span><br><span class="line">            <span class="comment">//如果k位置的点可以填充这个颜色</span></span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                color[k]++;<span class="comment">//不可填充这个颜色，搜索下一个颜色</span></span><br><span class="line">        &#125;<span class="comment">///挑选合适颜色</span></span><br><span class="line">        <span class="keyword">if</span>(color[k] &lt;= m &amp;&amp; k == n)</span><br><span class="line">        &#123; <span class="comment">///找完则输出</span></span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)<span class="comment">//输出点1到点n所填充的颜色</span></span><br><span class="line">                <span class="built_in">printf</span>(<span class="string">"%d "</span>,color[i]);</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">"\n"</span>);</span><br><span class="line">            cnt++;<span class="comment">//计数加一</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(color[k] &lt;= m &amp;&amp; k &lt; n)</span><br><span class="line">        &#123;<span class="comment">//没找完所有的点</span></span><br><span class="line">            k++;<span class="comment">///染下一个顶点</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">        &#123;<span class="comment">//颜色超出或者个数超出时，这个k点回溯上一个点k-1</span></span><br><span class="line">            color[k]=<span class="number">0</span>;<span class="comment">///回溯,变为未填充状态找其他方法</span></span><br><span class="line">            k--;<span class="comment">//找上一个点</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> cnt;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n,m,i,j;</span><br><span class="line">    <span class="keyword">int</span> c[<span class="number">100</span>][<span class="number">100</span>];</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"输入顶点数n和着色数m:\n"</span>);</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">"%d %d"</span>,&amp;n,&amp;m);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"输入无向图的邻接矩阵:\n"</span>);</span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">        <span class="keyword">for</span>(j=<span class="number">1</span>;j&lt;=n;j++)</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;c[i][j]);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"各个点所着颜色的所有解:\n"</span>);</span><br><span class="line">    <span class="keyword">int</span> cnt=graphColor(n,m,c);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"方案数: %d\n"</span>,cnt);</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">///图着色问题回溯法</span></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> 无向图邻接矩阵示例</span></span><br><span class="line"><span class="comment"> 1 0 0 0</span></span><br><span class="line"><span class="comment"> 1 0 1 0</span></span><br><span class="line"><span class="comment"> 0 0 1 0</span></span><br><span class="line"><span class="comment"> 0 0 1 0</span></span><br><span class="line"><span class="comment"> 1 1 0 0</span></span><br><span class="line"><span class="comment"> */</span></span><br></pre></td></tr></table></figure>



<h2 id="马踏棋盘"><a href="#马踏棋盘" class="headerlink" title="马踏棋盘"></a>马踏棋盘</h2><h2 id="算24"><a href="#算24" class="headerlink" title="算24"></a>算24</h2><h2 id="算式拼凑"><a href="#算式拼凑" class="headerlink" title="算式拼凑"></a>算式拼凑</h2><h3 id="1-2-3-4-5-6-7-8-9-110"><a href="#1-2-3-4-5-6-7-8-9-110" class="headerlink" title="1 2 3 4 5 6 7 8 9 = 110"></a>1 2 3 4 5 6 7 8 9 = 110</h3><h3 id="无优先级运算"><a href="#无优先级运算" class="headerlink" title="无优先级运算"></a>无优先级运算</h3><h2 id="全排列"><a href="#全排列" class="headerlink" title="全排列"></a>全排列</h2><h3 id="递归方法"><a href="#递归方法" class="headerlink" title="递归方法"></a>递归方法</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;string&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXN = <span class="number">20</span>;</span><br><span class="line"><span class="keyword">bool</span> visit[MAXN];<span class="comment">//存储字符的位置是否被访问</span></span><br><span class="line"><span class="keyword">char</span> sequence[MAXN];<span class="comment">//存储字符的结果</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">GetPermutation</span><span class="params">(<span class="built_in">string</span> str ,<span class="keyword">int</span> idx)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (idx &gt;= str.<span class="built_in">size</span>()) &#123;</span><br><span class="line">    <span class="comment">//如果当前下标超出字符串大小则表示成功找到一个全排列</span></span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; sequence &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; str.<span class="built_in">size</span>(); ++i) &#123;</span><br><span class="line">            <span class="keyword">if</span> (visit[i]) &#123;</span><br><span class="line">                <span class="keyword">continue</span>;<span class="comment">//如果当前字符已经被访问过，则跳过</span></span><br><span class="line">            &#125;</span><br><span class="line">            visit[i] = <span class="literal">true</span>;<span class="comment">//被访问了</span></span><br><span class="line">            sequence[idx] = str[i];</span><br><span class="line">            <span class="comment">//将当前没有被访问过的字符加入字符数组idx所指向的位置</span></span><br><span class="line">            GetPermutation(str, idx + <span class="number">1</span>);<span class="comment">//确定下一个位置</span></span><br><span class="line">            visit[i] = <span class="literal">false</span>;<span class="comment">//回溯</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    </span><br><span class="line">    <span class="built_in">string</span> str;</span><br><span class="line">    <span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; str) &#123;</span><br><span class="line">        <span class="built_in">memset</span>(visit, <span class="number">0</span>, <span class="keyword">sizeof</span>(visit));</span><br><span class="line">        sort(str.<span class="built_in">begin</span>(), str.<span class="built_in">end</span>());</span><br><span class="line">        GetPermutation(str, <span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="系统函数方法"><a href="#系统函数方法" class="headerlink" title="系统函数方法"></a>系统函数方法</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;string&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    </span><br><span class="line">    <span class="built_in">string</span> str;</span><br><span class="line">    <span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; str) &#123;</span><br><span class="line">        sort(str.<span class="built_in">begin</span>(), str.<span class="built_in">end</span>());</span><br><span class="line">        <span class="keyword">do</span> &#123;</span><br><span class="line">            <span class="built_in">cout</span> &lt;&lt; str &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">        &#125; <span class="keyword">while</span> (next_permutation(str.<span class="built_in">begin</span>(), str.<span class="built_in">end</span>()));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="八皇后"><a href="#八皇后" class="headerlink" title="八皇后"></a>八皇后</h2><h2 id="迷宫"><a href="#迷宫" class="headerlink" title="迷宫"></a>迷宫</h2><h2 id="八数码"><a href="#八数码" class="headerlink" title="八数码"></a>八数码</h2><h2 id="ROAD"><a href="#ROAD" class="headerlink" title="ROAD"></a>ROAD</h2><h2 id="作业调度问题"><a href="#作业调度问题" class="headerlink" title="作业调度问题"></a>作业调度问题</h2><p> 给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需(1≤i≤n)要机器j(1≤j≤2)的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。</p>
<p>|tji     |机器1 |    机器2|<br>|— |— |<br>|作业1       |2     |     1|<br>|作业2      |3     |           1|<br>|作业3      |2      |          3|</p>
<p>例如，对于这张表格所示的情况，3个作业有3!=6种可能调度方案，很显然最坏复杂度即为O(n!)。如果按照2,3,1的顺序,则作业2的完成时间为4，作业3的完成时间为8，作业1的完成时间为9，完成时间和为21。最优的作业调度顺序为最佳调度方案是1,3,2，其完成时间和为18。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXN = <span class="number">100</span>;</span><br><span class="line"><span class="keyword">int</span> n;<span class="comment">//作业数量</span></span><br><span class="line"><span class="keyword">int</span> x[MAXN];<span class="comment">//记录当前调度序号</span></span><br><span class="line"><span class="keyword">int</span> cost[MAXN][<span class="number">3</span>];<span class="comment">//cost[j][i]表示作业j在第i台机器上的处理时间</span></span><br><span class="line"><span class="keyword">int</span> lowest = <span class="number">10000</span>;<span class="comment">//最小处理时间</span></span><br><span class="line"><span class="keyword">int</span> visit[MAXN];<span class="comment">//调度作业顺序</span></span><br><span class="line"><span class="keyword">int</span> curtime = <span class="number">0</span>;<span class="comment">//当前已完成的所有作业的完成时间和</span></span><br><span class="line"><span class="keyword">int</span> f1 = <span class="number">0</span>,f2 = <span class="number">0</span>;<span class="comment">//f1为调度到作业j时，机器1上的纯处理时间之和</span></span><br><span class="line"><span class="comment">//f2为作业j的完成时间</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Backtrace</span><span class="params">(<span class="keyword">int</span> k)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> temp;</span><br><span class="line">    <span class="keyword">if</span> (k &gt; n) &#123;<span class="comment">//到达叶子结点，达到最底部</span></span><br><span class="line">        <span class="keyword">if</span> (curtime &lt; lowest) &#123;</span><br><span class="line">            lowest = curtime;<span class="comment">//保存调度最短时间</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i) &#123;</span><br><span class="line">                visit[i] = x[i];<span class="comment">//存储当前调度作业顺序</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span>&#123;<span class="comment">//非叶子结点，需要全排列，从k位置开始</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = k; j &lt;= n; ++j) &#123;</span><br><span class="line"><span class="comment">//只算作业在机器1的总处理时间，相当于机器1从开始一直运行到作业j用完机器1所消耗的时间</span></span><br><span class="line">            f1 += cost[x[j]][<span class="number">1</span>];</span><br><span class="line">            temp = f2;<span class="comment">//temp存储上一个作业在机器2的完成处理时间</span></span><br><span class="line"><span class="comment">//观察在机器1运行完的时间更长还是完成上一个作业（f2）的时间更长</span></span><br><span class="line"><span class="comment">//更长的那个时间 + 机器2处理的时间 = 作业j按当前调度的完成时间</span></span><br><span class="line">            f2 = (f1 &gt; f2 ? f1 : f2) + cost[x[j]][<span class="number">2</span>];<span class="comment">//f2为当前作业完成时间</span></span><br><span class="line">            curtime += f2;<span class="comment">//算出调度到作业j的完成时间和 = 每个作业完成时间之和</span></span><br><span class="line">            <span class="keyword">if</span> (curtime &lt; lowest) &#123;<span class="comment">//如果当前的完成时间小于之前的最少处理时间，则继续搜索</span></span><br><span class="line">                swap(x[j], x[k]);<span class="comment">//交换两个作业序号的位置</span></span><br><span class="line">                Backtrace(k + <span class="number">1</span>);</span><br><span class="line">                swap(x[j], x[k]);<span class="comment">//交换回来准备回溯</span></span><br><span class="line">            &#125;<span class="comment">//回溯，将值复原到进入这个循环结构之前</span></span><br><span class="line">            curtime -= f2;</span><br><span class="line">            f2 = temp;</span><br><span class="line">            f1 -= cost[x[j]][<span class="number">1</span>];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"请输入作业数量"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="built_in">cin</span> &gt;&gt; n;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"请输入在各机器上的处理时间"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span> ; i &lt;= <span class="number">2</span>; ++i) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= n ; ++j) &#123;</span><br><span class="line">            <span class="built_in">cin</span> &gt;&gt; cost[j][i];<span class="comment">//输入作业j在及其i的耗时</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;=n; ++i) &#123;</span><br><span class="line">        x[i] = i;</span><br><span class="line">    &#125;</span><br><span class="line">    Backtrace(<span class="number">1</span>);</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"调度作业顺序"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i) &#123;</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; visit[i] &lt;&lt; <span class="string">" "</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"处理时间"</span> &lt;&lt; <span class="built_in">endl</span> &lt;&lt; lowest;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> 请输入作业数量</span></span><br><span class="line"><span class="comment"> 3</span></span><br><span class="line"><span class="comment"> 请输入在各机器上的处理时间</span></span><br><span class="line"><span class="comment"> 2 3 2</span></span><br><span class="line"><span class="comment"> 1 1 3</span></span><br><span class="line"><span class="comment"> 调度作业顺序</span></span><br><span class="line"><span class="comment"> 1    3    2</span></span><br><span class="line"><span class="comment"> 处理时间:</span></span><br><span class="line"><span class="comment"> 18</span></span><br><span class="line"><span class="comment"> */</span></span><br></pre></td></tr></table></figure>

<h2 id="符号三角形"><a href="#符号三角形" class="headerlink" title="符号三角形"></a>符号三角形</h2><p>题目： 下面都是“-”。 下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。 </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">+   +   -   +   -   +   +</span><br><span class="line"></span><br><span class="line">   +   -   -   -   -   +</span><br><span class="line"></span><br><span class="line">     -   +   +   +   -</span><br><span class="line">   </span><br><span class="line">       -   +   +   -</span><br><span class="line">   </span><br><span class="line">         -   +   -</span><br><span class="line">   </span><br><span class="line">           -   -</span><br><span class="line">   </span><br><span class="line">             +</span><br></pre></td></tr></table></figure>

<p>在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。</p>
<p>思路：</p>
<ol>
<li><p>根据第一行的前t个字符来确定一个符号三角形</p>
</li>
<li><p>通过前t个字符的符号三角形确定前t+1个字符的符号三角形</p>
<p>① 确定好第t+1个字符之后，在前面已经确定的符号三角形右边加一条边扩展而成</p>
<p>② 最终由前n个字符构成的符号三角形所确定的符号三角形包含的“+”个数与“-”的个数同为n(n+1)/4,因此在回溯的过程中用当前字符构成的符号三角形所确定的符号三角形中包含的“+”个数与“-”的个数均不超过n(n+1)/4作为可行性约束，用于减去不满足约束的子树。</p>
<p>③ 对于给定的n，当n(n+1)/2为奇数时，显然不包括“+”个数与“-”的个数相同的情况，输出错误信息</p>
</li>
<li><p>变量说明：</p>
<p>Backtrack(int k,int sum)</p>
<p>函数作用：由前k-1个字符构成的符号三角形通过第k个字符来扩展符号三角形</p>
<p>失败退出回溯条件：</p>
<p>​    ① “+”个数（即sum的值）&gt; n(n+1)/4;</p>
<p>​    ② 或者 k*(k-1)/2 - sum &gt; n(n+1)/4;</p>
<p>成功退出回溯条件：</p>
<p>​    k &gt; n时：当前已找到的符号三角形个数ans + 1</p>
<p>k &lt;= n 时：</p>
<p>当前扩展结点Z是解空间的内部结点，有s[1][t] = 1 和 s[1][t] = 0 共2个儿子结点</p>
<p>对当前扩展结点Z的每个儿子结点，计算其相应的符号三角形中“+”个数sum</p>
</li>
</ol>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iomanip&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXN = <span class="number">100</span>;</span><br><span class="line"><span class="keyword">int</span> ans = <span class="number">0</span>,half,n;</span><br><span class="line"><span class="keyword">int</span> s[MAXN][MAXN];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Backtrack</span><span class="params">(<span class="keyword">int</span> k,<span class="keyword">int</span> sum)</span></span>&#123;<span class="comment">//t为第一行的第t个字符，sum为当前扫描的符号“+”比"-"多的个数</span></span><br><span class="line">    <span class="keyword">if</span> (sum &gt; half || k * (k - <span class="number">1</span>) / <span class="number">2</span> - sum &gt; half ) &#123;</span><br><span class="line">        <span class="comment">//当前填充字符中</span></span><br><span class="line">        <span class="comment">//“+”号元素大于n * (n + 1) / 4</span></span><br><span class="line">        <span class="comment">//或者 “-”号元素大于n * (n + 1) / 4</span></span><br><span class="line">        <span class="keyword">return</span>;<span class="comment">//已经算出的子树不满足，剪枝</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (k &gt; n) &#123;<span class="comment">//满足要求，相等</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i) &#123;<span class="comment">//输出满足条件的矩阵</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= n - i + <span class="number">1</span>; ++j) &#123;</span><br><span class="line">                <span class="built_in">cout</span> &lt;&lt; s[i][j] &lt;&lt; <span class="string">" "</span>;<span class="comment">//输出一行</span></span><br><span class="line">            &#125;</span><br><span class="line">            <span class="built_in">cout</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">            <span class="keyword">if</span> (i != n) &#123;</span><br><span class="line">                <span class="built_in">cout</span> &lt;&lt; setw(i + <span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;<span class="comment">//for</span></span><br><span class="line">        ans++;</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">2</span> ; ++i) &#123;</span><br><span class="line">        s[<span class="number">1</span>][k] = i;<span class="comment">////让第一行第t个字符为i</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">2</span>; j &lt;= k; ++j) &#123;<span class="comment">//从第二行到第t行的赋值</span></span><br><span class="line">            s[j][k - j + <span class="number">1</span>] = s[j - <span class="number">1</span>][k - j + <span class="number">1</span>] ^ s[j - <span class="number">1</span>][k - j + <span class="number">2</span>];</span><br><span class="line">            <span class="comment">//递推子树，2个同号下面都是“+”，2个异号下面都是“-”。</span></span><br><span class="line">            sum += s[j][k - j + <span class="number">1</span>];<span class="comment">//sum加上新赋值的元素</span></span><br><span class="line">        &#125;</span><br><span class="line">        Backtrack(k + <span class="number">1</span>, sum + i);<span class="comment">//给第一行第k+1个位置加上i，sum的新值为sum + i</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">2</span>; j &lt;= k; ++j) &#123;<span class="comment">//回溯时取消上一次的赋值</span></span><br><span class="line">            sum -= s[j][k - j + <span class="number">1</span>];<span class="comment">//sum减去之前赋值的元素</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (<span class="built_in">cin</span> &gt;&gt; n) &#123;<span class="comment">//n为输入的第一行的个数</span></span><br><span class="line">        half = n * (n + <span class="number">1</span>) / <span class="number">2</span>;<span class="comment">//填充符号的个数</span></span><br><span class="line">        <span class="built_in">memset</span>(s, <span class="number">0</span>, <span class="keyword">sizeof</span>(s));</span><br><span class="line">        <span class="keyword">if</span> (half % <span class="number">2</span> == <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="built_in">cout</span> &lt;&lt; <span class="number">0</span>;<span class="comment">//总数是奇数直接判0</span></span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            half /= <span class="number">2</span>;<span class="comment">//half修改为总数的一半</span></span><br><span class="line">            Backtrack(<span class="number">1</span>, <span class="number">0</span>);</span><br><span class="line">            <span class="built_in">cout</span> &lt;&lt; <span class="string">"满足条件的三角形的个数是："</span> &lt;&lt; <span class="built_in">endl</span> &lt;&lt; ans;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="最大团问题"><a href="#最大团问题" class="headerlink" title="最大团问题"></a>最大团问题</h2><p>给定无向图G=(V,E)。如果U∈ V，且对任意u, v ∈ U 有 (u,v) ∈ E，则称U是G的完全子图。G的完全子图U是G的团，当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。</p>
<p>Input</p>
<p>输入的第一行为测试样例的个数T ，接下来有T个测试样例。每个测试样例的第一行是 顶点数n 和 边数m （ n ≤ 20，m ≤ 400 ），接下来m行，每行两个整数u和v，表示顶点u和v之间有一条边相连。（ 1 ≤ u &lt; v ≤ n ）。<br>Output</p>
<p>对应每个测试样例输出两行，第一行格式为”Case #: M”，其中’#’表示第几个测试样例（从1开始计），M为最大团顶点数。<br>Sample Input</p>
<p>1<br>5 7<br>1 2<br>1 4<br>1 5<br>2 3<br>2 5<br>3 5<br>4 5</p>
<p>Sample Output</p>
<p>Case 1: 3</p>
<p>题意分析：</p>
<p>完全子图即是图中任意的两个顶点都有连接，与完全图是一样的。</p>
<p>思路：<br>    每次都放一个点进入图中，因为是无向图所以其生成的是子集树，只需要把所有点都放进图中尝试一次便可。剪枝部分使用简单的剪枝，即没试过的点+图中的点&lt;当前最优的点即可符合，否则直接跳过该点，尝试下一个点</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="keyword">int</span> book[<span class="number">25</span>][<span class="number">25</span>],vist[<span class="number">25</span>],que[<span class="number">25</span>];</span><br><span class="line"><span class="comment">//que数组表示当前极大团中的点，book邻接矩阵记录边，vist记录访问过的点</span></span><br><span class="line"><span class="keyword">int</span> n,m,maxx;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> sum)</span></span>&#123;</span><br><span class="line"><span class="comment">//对顶点x邻接的边进行搜索，当前极大团的顶点数为sum</span></span><br><span class="line">    <span class="keyword">if</span>(x&gt;n)&#123;<span class="comment">//搜完所有的点，递归出口</span></span><br><span class="line">        maxx=sum;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> vt=<span class="number">0</span>;<span class="comment">//标志位</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;sum;j++)&#123;<span class="comment">//判断x是否与当前极大团的每个顶点邻接</span></span><br><span class="line">        <span class="keyword">if</span>(book[x][que[j]] == <span class="number">0</span>)&#123;<span class="comment">//都不邻接时置vt为1，跳出循环</span></span><br><span class="line">            vt=<span class="number">1</span>;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(vt == <span class="number">0</span>)</span><br><span class="line">    &#123;<span class="comment">//相通进入que极大团数组，并且图中顶点+1</span></span><br><span class="line">        vist[x]=<span class="number">1</span>;<span class="comment">//访问数组标记</span></span><br><span class="line">        que[sum]=x;<span class="comment">//加入到极大团中</span></span><br><span class="line">        dfs(x+<span class="number">1</span>,sum+<span class="number">1</span>);<span class="comment">//对顶点x+1进行搜索</span></span><br><span class="line">    &#125;</span><br><span class="line"><span class="comment">//若 未尝试的点 + 极大团的点 &lt; 当前最优的点则剪枝</span></span><br><span class="line"><span class="comment">//其他条件表示有可能有最大点,尝试下一个点，当前极大团不动</span></span><br><span class="line">    <span class="keyword">if</span>(sum + n - x &gt; maxx)</span><br><span class="line">        dfs(x + <span class="number">1</span>,sum);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> t,vi=<span class="number">0</span>;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;t);</span><br><span class="line">    <span class="keyword">while</span>(t--)&#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">"%d %d"</span>,&amp;n,&amp;m);</span><br><span class="line">        <span class="keyword">int</span> x,y;</span><br><span class="line">        <span class="built_in">memset</span>(vist,<span class="number">0</span>,<span class="keyword">sizeof</span>(vist));</span><br><span class="line">        <span class="built_in">memset</span>(book,<span class="number">0</span>,<span class="keyword">sizeof</span>(book));</span><br><span class="line">        maxx=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++)&#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%d %d"</span>,&amp;x,&amp;y);</span><br><span class="line">            book[x][y]=<span class="number">1</span>;</span><br><span class="line">            book[y][x]=<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        dfs(<span class="number">1</span>,<span class="number">0</span>);</span><br><span class="line">        vi++;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">"Case %d: %d\n"</span>,vi,maxx);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="货郎问题"><a href="#货郎问题" class="headerlink" title="货郎问题"></a>货郎问题</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;  </span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX 1000  </span></span><br><span class="line"><span class="keyword">int</span> g[<span class="number">100</span>][<span class="number">100</span>], x[<span class="number">100</span>], bestx[<span class="number">100</span>];</span><br><span class="line"><span class="keyword">int</span> cl = <span class="number">0</span>, bestl = MAX, n;</span><br><span class="line"><span class="comment">//界定函数</span></span><br><span class="line"><span class="function"><span class="keyword">double</span> <span class="title">Bound</span><span class="params">(<span class="keyword">int</span> t, <span class="keyword">int</span> cl)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">double</span> min1 = <span class="number">0</span>, min2 = <span class="number">0</span>, tempSum=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> j = t; j &lt;= n; j++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span> (g[x[t - <span class="number">1</span>]][x[j]] != <span class="number">-1</span> &amp;&amp; g[x[t - <span class="number">1</span>]][x[j]] &lt; min1)</span><br><span class="line">		&#123;</span><br><span class="line">			min1 = g[x[t - <span class="number">1</span>]][x[j]];</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">if</span> (g[x[j]][x[i]] != <span class="number">-1</span> &amp;&amp; g[x[j]][x[i]] &lt; min2)</span><br><span class="line">			&#123;</span><br><span class="line">				min2 = g[x[j]][x[i]];</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		tempSum += min2;</span><br><span class="line">	&#125;</span><br><span class="line"> </span><br><span class="line">	<span class="keyword">return</span> cl + min1 + tempSum;</span><br><span class="line"> </span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Traveling</span><span class="params">(<span class="keyword">int</span> t)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> j;</span><br><span class="line">	<span class="keyword">if</span> (t&gt;n) <span class="comment">//到达叶子结点  </span></span><br><span class="line">	&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">if</span> (g[x[n]][<span class="number">1</span>] != <span class="number">-1</span> &amp;&amp; (cl + g[x[n]][<span class="number">1</span>]&lt;bestl))</span><br><span class="line">            <span class="comment">//推销员到的最后一个城市与出发的城市之间有路径，且当前总距离比当前最优值小  </span></span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">for</span> (j = <span class="number">1</span>; j &lt;= n; j++)</span><br><span class="line">				bestx[j] = x[j];</span><br><span class="line">			bestl = cl + g[x[n]][<span class="number">1</span>];</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span>    <span class="comment">//没有到达叶子结点  </span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">for</span> (j = t; j &lt;= n; j++)<span class="comment">//搜索扩展结点的左右分支，即所有与当前所在城市临近的城市  </span></span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">if</span> (g[x[t - <span class="number">1</span>]][x[j]] != <span class="number">-1</span> &amp;&amp; Bound(t, cl)&lt;bestl)</span><br><span class="line">			<span class="comment">//if (g[x[t - 1]][x[j]] != -1 &amp;&amp; (cl + g[x[t - 1]][x[j]]&lt;bestl))</span></span><br><span class="line">             <span class="comment">//如果第t-1个城市与第t个城市之间有路径且可以得到更短的路线  </span></span><br><span class="line">			&#123;</span><br><span class="line"> </span><br><span class="line">				swap(x[t], x[j]);     <span class="comment">//保存要去的第t个城市到x[t]中  </span></span><br><span class="line">				cl += g[x[t - <span class="number">1</span>]][x[t]]; <span class="comment">//路线长度增加  </span></span><br><span class="line">				Traveling(t + <span class="number">1</span>);      <span class="comment">//搜索下一个城市  </span></span><br><span class="line">				cl -= g[x[t - <span class="number">1</span>]][x[t]];</span><br><span class="line">				swap(x[t], x[j]);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> i, j;</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"请输入一共有几个城市："</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	<span class="built_in">cin</span> &gt;&gt; n;</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"请输入城市之间的距离"</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line"> </span><br><span class="line">	<span class="keyword">for</span> (i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">		<span class="keyword">for</span> (j = <span class="number">1</span>; j &lt;= n; j++)</span><br><span class="line">			<span class="built_in">cin</span> &gt;&gt; g[i][j];</span><br><span class="line"> </span><br><span class="line">	<span class="keyword">for</span> (i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		x[i] = i;</span><br><span class="line">		bestx[i] = <span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line"> </span><br><span class="line">	Traveling(<span class="number">2</span>);</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"城市路线："</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	<span class="keyword">for</span> (i = <span class="number">1</span>; i &lt;= n; i++)</span><br><span class="line">		<span class="built_in">cout</span> &lt;&lt; bestx[i] &lt;&lt; <span class="string">' '</span>;</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; bestx[<span class="number">1</span>];</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; <span class="string">"最短路线长度："</span> &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	<span class="built_in">cout</span> &lt;&lt; bestl &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="圆排列问题"><a href="#圆排列问题" class="headerlink" title="圆排列问题"></a>圆排列问题</h2><p>给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为2+4sqrt(2)</p>
<p><img src="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200325133716157.png" alt="image-20200325133716157"></p>
<p><img src="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200325135817004.png" alt="image-20200325135817004"></p>
<p>center函数：center计算圆在当前圆排列中的横坐标，由x^2 = sqrt((r1+r2)^2-(r1-r2)^2)推导出x = 2 * sqrt(r1 * r2)。为啥要把计算圆心坐标的公式放在一个for循环里面呢？我们很容易会有一个先入为主的思想，那就是后一个圆必然与排在它前一个位置的圆相切，其实排在任意位置的圆与其前或后的任意一个圆都有可能相切的，画个图就很清晰了。只要大小合适，目标圆就有可能与排列中的任意一个圆相切。</p>
<p><img src="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200325135653425.png" alt="image-20200325135653425"></p>
<p>compute函数：可以想象其中任意的一个圆无限大或无限小，无限大的话那其余的圆就可以统统忽略了。因为已知所有圆的x[]和r[],很容易求出每个圆的左右坐标，通过比较找出最小的左部坐标和最大的右部坐标，一减就是该圆排列的长度，然后把每次不同的排列长度相比较，找到更小的minlen就更新。</p>
<p><img src="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200325133826887.png" alt="image-20200325133826887"></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cmath&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXN = <span class="number">100</span>;</span><br><span class="line"><span class="keyword">int</span> n;<span class="comment">//圆的个数</span></span><br><span class="line"><span class="keyword">double</span> minlen=<span class="number">1000000</span>,x[MAXN],r[MAXN];<span class="comment">//分别为最小圆排列长度，每个圆心横坐标数组，每个圆半径数组</span></span><br><span class="line"><span class="keyword">double</span> bestv[MAXN];<span class="comment">//最小圆排列的半径顺序</span></span><br><span class="line"><span class="function"><span class="keyword">double</span> <span class="title">center</span><span class="params">(<span class="keyword">int</span> t)</span></span>&#123;<span class="comment">//得到第t个圆的圆心横坐标</span></span><br><span class="line">    <span class="keyword">double</span> tmp = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; t; ++i) &#123;<span class="comment">//计算第t个圆与前面(序号为1~t-1)已排列圆相切时的距离，求最大距离</span></span><br><span class="line">        <span class="keyword">double</span> xvalue = x[i] + <span class="number">2.0</span> * <span class="built_in">sqrt</span>(r[i]*r[t]);<span class="comment">//计算第t个圆与第i个圆相切时的距离</span></span><br><span class="line">        <span class="keyword">if</span> (xvalue &gt; tmp) &#123;<span class="comment">//最大的距离就是圆心坐标</span></span><br><span class="line">            tmp = xvalue;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> tmp;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">compute</span><span class="params">()</span></span>&#123;<span class="comment">//计算圆排列长度</span></span><br><span class="line">    <span class="keyword">double</span> low=<span class="number">0</span>,high=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i) &#123;<span class="comment">//寻找最左端与最右端的距离</span></span><br><span class="line">        <span class="keyword">if</span> (x[i] - r[i] &lt; low) &#123;</span><br><span class="line">            low = x[i] - r[i];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (x[i] + r[i] &gt; high) &#123;</span><br><span class="line">            high = x[i] + r[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (high - low &lt; minlen) &#123;</span><br><span class="line">        minlen = high - low;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i) &#123;</span><br><span class="line">            bestv[i] = r[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Backtrack</span><span class="params">(<span class="keyword">int</span> t)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (t &gt; n)</span><br><span class="line">        compute();</span><br><span class="line">    <span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = t; i &lt;= n; ++i) &#123;</span><br><span class="line"><span class="comment">//确保全排列：一开始按顺序的时候没交换，第一次排列后，回溯时i与t不同</span></span><br><span class="line">            swap(r[t], r[i]);</span><br><span class="line">            <span class="keyword">double</span> centerx = center(t);<span class="comment">//计算第t个圆的横坐标</span></span><br><span class="line">            <span class="keyword">if</span> (centerx + r[<span class="number">1</span>] + r[t] &lt; minlen) &#123;<span class="comment">//剪枝</span></span><br><span class="line">                x[t] = centerx;<span class="comment">//确定了加入第t个圆的圆排列长度</span></span><br><span class="line">                Backtrack(t + <span class="number">1</span>);<span class="comment">//搜索下一个圆</span></span><br><span class="line">            &#125;</span><br><span class="line">            swap(r[t], r[i]);<span class="comment">//回溯，将前面全排列结束后复原，再接着从更前一个元素开始排列</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"圆的个数 n："</span>;</span><br><span class="line">    <span class="built_in">cin</span> &gt;&gt; n;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"每个圆的半径分别为："</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i) &#123;</span><br><span class="line">        <span class="built_in">cin</span> &gt;&gt; r[i];</span><br><span class="line">    &#125;</span><br><span class="line">    Backtrack(<span class="number">1</span>);</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"最小圆排列长度为："</span> &lt;&lt; minlen &lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; <span class="string">"最优圆排列的顺序对应的半径分别为："</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i) &#123;</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; bestv[i] &lt;&lt; <span class="string">" "</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="连续邮资问题"><a href="#连续邮资问题" class="headerlink" title="连续邮资问题"></a>连续邮资问题</h2><p>假设国家发行了k种不同面值的邮票，并且规定每张信封上最多只允许贴h张邮票。连续邮资问题要求对于给定的k和h的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当k=5和h=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。（UVA165）</p>
<p><img src="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200326170059426.png" alt="image-20200326170059426"></p>
<p>思路概括：</p>
<ul>
<li><p>用stampval来保存各个面值，用maxval来保存当前所有面值能组成的最大连续面值。</p>
</li>
<li><p>stampval[0] 一定等于1，因为1是最小的正整数。相应的，maxval[0]=1*h。接下去就是确定第二个，第三个……第k个邮票的面值了。对于stampval[i+1]，它的取值范围stampval[i]+1~maxval[i]+1。 </p>
</li>
<li><p>stampval[i]+1是因为这一次取的面值肯定要比上一次的面值大，而这次取的面值的上限是上次能达到的最大连续面值+1， 是因为如果比这个更大的话， 那么就会出现断层， 即无法组成上次最大面值+1这个数了。 </p>
</li>
<li><p>举个例子， 假设可以贴3张邮票，有3种面值，前面2种面值已经确定为1,2， 能达到的最大连续面值为6， 那么接下去第3种面值的取值范围为3～7。如果取得比7更大的话会怎样呢？ 动手算下就知道了，假设取8的话， 那么面值为1,2,8，将无法组合出7。直接递归回溯所有情况， 便可知道最大连续值了。</p>
</li>
</ul>
<p><img src="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200326170152534.png" alt="image-20200326170152534"></p>
<p><img src="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200326170523901.png" alt="image-20200326170523901"></p>
<h3 id="回溯法"><a href="#回溯法" class="headerlink" title="回溯法"></a>回溯法</h3><p>变量说明：</p>
<ul>
<li>ans为最终方案的面值组合,maxStampVal是最终方案的最大面值</li>
<li>stampVal[1~n]来保存各个邮票面值，maxVal[1~n]来保存当前所有面值能组成的最大连续面值</li>
<li>stampVal[1]一定是等于1的。因为如果没有1的话，很多数字都不能凑成</li>
<li>maxVal[1] = 1*h ,h为允许贴邮票的数量</li>
<li>对于stampVal[i+1],它的取值范围是stampVal[i]+1 ~maxVal[i]+1.</li>
<li>occur是一个全局数组,调用递归时先初始化为0,然后用它来记录出现过的面值之和，最后只需要从occur数组的下标1开始枚举，直到不是true值时就是能达到的最大连续面值。</li>
</ul>
<p>回溯过程：（进行到第cur种面额邮票时）</p>
<ul>
<li>cur &gt; n 时：算法搜索到叶结点，得到新的邮票面值设计方案x[1:n]。如果该方案能够给出的最大连续邮资区间大于当前已找到的最大连续邮资区间maxvalue，则更新当前最优值maxvalue和相应的最优解ans。</li>
<li>cur &lt;= n 时：当前扩展结点Z是解空间的内部节点。在该节点处，x[1:cur-1]能给出的最大连续邮资区间为r-1因此，在结点Z处，x[i]的可取值范围是[x[cur-1] + 1 : r + 1]，从而，结点Z有r - x[cur-1]个儿子节点。算法对当前扩展结点Z的每个儿子结点，以深度优先的方式递归地对相应子树进行搜索</li>
</ul>
<p>dfs(int mcur, int n, int sum)说明：</p>
<ul>
<li>计算给定面额种类下，最大数量不超过m时，当前数量为mcur时能够达到的最大连续面值sum</li>
<li>当前用了mcur张邮票，在当前邮票种类数 n下，面额之和是sum</li>
<li>mcur &gt;= m 时：达到了单种邮票的最大张数，记录当前总的面额sum</li>
<li>mcur &lt; m 时：<ul>
<li>记录记录当前总的面额sum</li>
<li>将其他种类的邮票各加一张进行深度优先搜索</li>
</ul>
</li>
</ul>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXN = <span class="number">200</span>;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> m, n;</span><br><span class="line"><span class="keyword">int</span> ans[MAXN], maxStampVal, stampVal[MAXN], maxVal[MAXN];<span class="comment">//从下标1开始赋值</span></span><br><span class="line"><span class="keyword">bool</span> occur[MAXN];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> mcur, <span class="keyword">int</span> n, <span class="keyword">int</span> sum)</span></span>&#123;</span><br><span class="line">    <span class="comment">// mcur当前用了几张票， n当前面额种类数， sum面额之和</span></span><br><span class="line">    <span class="comment">// 计算给定面额和数量能够达到的最大连续面值</span></span><br><span class="line">    <span class="keyword">if</span>(mcur &gt;= m)&#123;<span class="comment">//达到单种邮票的最大张数</span></span><br><span class="line">        occur[sum] = <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    occur[sum] = <span class="literal">true</span>;<span class="comment">//sum面额可以达到</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i)&#123;<span class="comment">//一张一张地增加</span></span><br><span class="line">        dfs(mcur + <span class="number">1</span>, n, sum + stampVal[i]);<span class="comment">//面额种类加1，面额之和需加上当前邮票面额</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">search</span><span class="params">(<span class="keyword">int</span> cur)</span></span>&#123;<span class="comment">//在 第cur种 邮票下进行搜索</span></span><br><span class="line">    <span class="keyword">if</span>(cur &gt; n)&#123;<span class="comment">//已经达到最大邮票种类数，cur = n + 1</span></span><br><span class="line">        <span class="keyword">if</span>(maxVal[cur - <span class="number">1</span>] &gt; maxStampVal)&#123;<span class="comment">//如果第n张邮票的最大连续面额为当前最大</span></span><br><span class="line">            maxStampVal = maxVal[cur - <span class="number">1</span>];<span class="comment">//更新最大连续面额</span></span><br><span class="line">            <span class="built_in">memcpy</span>(ans, stampVal, <span class="keyword">sizeof</span>(stampVal));<span class="comment">//将邮票面额组合赋值给ans</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = stampVal[cur - <span class="number">1</span>] + <span class="number">1</span>; i &lt;= maxVal[cur - <span class="number">1</span>] + <span class="number">1</span>; ++i)&#123;</span><br><span class="line">        <span class="comment">//对第cur种面额的可取值范围进行最大连续面额的搜索</span></span><br><span class="line">        <span class="built_in">memset</span>(occur, <span class="number">0</span>, <span class="keyword">sizeof</span>(occur));<span class="comment">//每一次新的面额下都要初始化出现数组</span></span><br><span class="line">        stampVal[cur] = i;<span class="comment">//第cur个邮票面值为 i</span></span><br><span class="line">        dfs(<span class="number">0</span>, cur, <span class="number">0</span>);<span class="comment">//进行张数的搜索</span></span><br><span class="line">        <span class="keyword">int</span> num=<span class="number">0</span>, j=<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span>(occur[j++]) ++num;<span class="comment">//寻找第一个没有连续访问的面额num</span></span><br><span class="line">        maxVal[cur] = num;<span class="comment">//第cur种邮票的最大面额为num</span></span><br><span class="line">        search(cur+<span class="number">1</span>);<span class="comment">//对第cur+1种邮票进行搜索</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="comment">//n面额数，m每种邮票可以使用的数量</span></span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">"%d %d"</span>, &amp;n, &amp;m)!=EOF)&#123;</span><br><span class="line">        stampVal[<span class="number">1</span>] = <span class="number">1</span>;</span><br><span class="line">        maxVal[<span class="number">1</span>] = m;</span><br><span class="line">        maxStampVal = <span class="number">-1</span>;</span><br><span class="line">        search(<span class="number">2</span>);</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; ++i)</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">"%3d"</span>, ans[i]);</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">" -&gt;%3d\n"</span>, maxStampVal);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="回溯法-动态规划法"><a href="#回溯法-动态规划法" class="headerlink" title="回溯法+动态规划法"></a>回溯法+动态规划法</h3><p>设不超过m张面值为x[1:i]的邮票贴出邮资j所需的最少邮票数为y[j]。通过y[j]可以很快推出r的值。事实上，y[j]可以通过递推在O(n)时间内解决：</p>
<p><img src="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/image-20200326145529471.png" alt="image-20200326145529471"></p>
<p>类似于0-1背包问题：</p>
<ul>
<li>y[j]表示贴上去的邮资j时的最小耗费邮票数，类似背包问题中的w[j]表示价值为j时的最小重量</li>
<li>y[j+x[i-1] * k] = min(y[j+x[i-1] * k],y[j] + k)，类似背包问题中的w[j] =  min(w[j-val[i-1]],w[j])</li>
<li>初始化y[j]时，意味着在只有m张面额为1的邮票下，贴上去的邮资为j时的最小耗费邮票数，即y[j] = j</li>
<li>最大连续邮资为r，maxVal[cur] = r</li>
</ul>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>; j&lt;= x[i<span class="number">-2</span>]*(m<span class="number">-1</span>);j++)</span><br><span class="line">        <span class="keyword">if</span> (y[j]&lt;m)</span><br><span class="line">          <span class="keyword">for</span> (<span class="keyword">int</span> k=<span class="number">1</span>;k&lt;=m-y[j];k++)</span><br><span class="line">            <span class="keyword">if</span> (y[j]+k&lt;y[j+x[i<span class="number">-1</span>]*k]) y[j+x[i<span class="number">-1</span>]*k]=y[j]+k;</span><br><span class="line">      <span class="keyword">while</span> (y[r]&lt;maxint) r++;</span><br></pre></td></tr></table></figure>

<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdlib&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INF 2147483647</span></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXN = <span class="number">2000</span>;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> m, n;</span><br><span class="line"><span class="keyword">int</span> ans[MAXN], maxStampVal, stampVal[MAXN], maxVal[MAXN], y[MAXN];</span><br><span class="line"><span class="keyword">bool</span> occur[MAXN];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">search</span><span class="params">(<span class="keyword">int</span> cur)</span></span>&#123;<span class="comment">//搜索前cur种邮票的最大连续邮资</span></span><br><span class="line">    <span class="keyword">if</span>(cur &gt; n)&#123;</span><br><span class="line">        <span class="keyword">if</span>(maxVal[cur<span class="number">-1</span>] &gt; maxStampVal)&#123;</span><br><span class="line">            maxStampVal = maxVal[cur<span class="number">-1</span>];</span><br><span class="line">            <span class="built_in">memcpy</span>(ans, stampVal, <span class="keyword">sizeof</span>(stampVal));</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> tmp[MAXN];<span class="comment">//tmp存储当前y数组,为接下来回溯后返回用</span></span><br><span class="line">    <span class="built_in">memcpy</span>(tmp, y, <span class="keyword">sizeof</span>(y));</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = stampVal[cur - <span class="number">1</span>] + <span class="number">1</span>; i &lt;= maxVal[cur - <span class="number">1</span>] + <span class="number">1</span>; ++i)&#123;</span><br><span class="line">        <span class="comment">//对第cur种面额的可取值范围进行最大连续面额的搜索</span></span><br><span class="line">        stampVal[cur] = i;<span class="comment">//第cur个邮票面值为 i</span></span><br><span class="line">        <span class="comment">// 关键步骤，利用了动态规划的思想</span></span><br><span class="line">        <span class="comment">//设不超过m张面值为x[1:i]的邮票贴出邮资j所需的最少邮票数为y[j]</span></span><br><span class="line">        <span class="comment">//y贴出的邮资为0~（第cur-1种邮票）*m</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; stampVal[cur - <span class="number">1</span>] * m; ++j)&#123;</span><br><span class="line">            <span class="keyword">if</span>(y[j] &lt; m)&#123;<span class="comment">//不超过m张的时候</span></span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> num = <span class="number">1</span>; num &lt;= m - y[j]; ++num)&#123;</span><br><span class="line">            <span class="comment">//num为可以贴上面额为i的邮票的数量</span></span><br><span class="line"><span class="comment">//如果最少邮票数y[j]添加num张邮票时的张数（y[j] + num）</span></span><br><span class="line"><span class="comment">//小于 y[j]再添加num张邮票时的邮资 的张数（y[j + i * num]）时，</span></span><br><span class="line"><span class="comment">//说明邮资为j + i * num时耗费的张数应该是更小的y[j] + num</span></span><br><span class="line">                <span class="keyword">if</span>(y[j] + num &lt; y[j + i * num] &amp;&amp; (j + i * num &lt; MAXN))</span><br><span class="line">                    y[j + i * num] = y[j] + num;</span><br><span class="line">            &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">int</span> r = maxVal[cur - <span class="number">1</span>];<span class="comment">//最大连续邮资为r</span></span><br><span class="line">        <span class="keyword">while</span>(y[r + <span class="number">1</span>] &lt; INF) r++;<span class="comment">//当y[r+1]有进行动态规划得到的值时，说明最大连续邮资可以到r+1</span></span><br><span class="line">        maxVal[cur] = r;<span class="comment">//当前的最大连续邮资为r</span></span><br><span class="line">        search(cur + <span class="number">1</span>);<span class="comment">//搜索cur+1时的情况</span></span><br><span class="line">        <span class="built_in">memcpy</span>(y, tmp, <span class="keyword">sizeof</span>(tmp));<span class="comment">//回溯y</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="comment">//n邮票面额种类数,m单种邮票最大张数</span></span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">"%d %d"</span>, &amp;n, &amp;m)!=EOF)&#123;</span><br><span class="line">        stampVal[<span class="number">1</span>] = <span class="number">1</span>;<span class="comment">//第一张邮票必须是1</span></span><br><span class="line">        maxVal[<span class="number">1</span>] = m;<span class="comment">//用m张面值为1的邮票组成的最大连续面额为m</span></span><br><span class="line">        <span class="keyword">int</span> i=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(i = <span class="number">0</span>; i &lt;= m; ++i)</span><br><span class="line">            y[i] = i;<span class="comment">//只有一张面值为1的邮票时，y[i]=i</span></span><br><span class="line">        <span class="keyword">while</span>(i &lt; MAXN) y[i++] = INF;<span class="comment">//其他y[i+1~MAXN]必须最大,方便之后选更小的</span></span><br><span class="line">        maxStampVal = <span class="number">-1</span>;</span><br><span class="line">        search(<span class="number">2</span>);</span><br><span class="line">        <span class="keyword">for</span>(i = <span class="number">1</span>; i &lt;= n; ++i)</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">"%3d"</span>, ans[i]);</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">" -&gt;%3d\n"</span>, maxStampVal);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/yangshucheng2020/tags/%E7%AE%97%E6%B3%95/" rel="tag"># 算法</a>
          
            <a href="/yangshucheng2020/tags/%E5%9B%9E%E6%BA%AF%E6%B3%95/" rel="tag"># 回溯法</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/yangshucheng2020/2020/03/27/%E6%95%B0%E5%AD%97%E7%BB%84%E5%90%88%E7%AD%89%E5%BC%8F%E9%97%AE%E9%A2%98/" rel="prev" title="数字排列组合问题">
                数字排列组合问题 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="https://gitee.com/yangshucheng2020/blogimage/raw/master/uPic/海绵jojo.jpg"
                alt="羊书change" />
            
              <p class="site-author-name" itemprop="name">羊书change</p>
              <p class="site-description motion-element" itemprop="description">记录生活</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/yangshucheng2020/archives/%7C%7Carchive">
              
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/yangshucheng2020/categories/index.html">
                  <span class="site-state-item-count">1</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/yangshucheng2020/tags/index.html">
                  <span class="site-state-item-count">16</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/yangshucheng1219" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="mailto:ysc714@163.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#循环赛制"><span class="nav-number">1.</span> <span class="nav-text">循环赛制</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#装载问题"><span class="nav-number">2.</span> <span class="nav-text">装载问题</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#简单回溯法"><span class="nav-number">2.1.</span> <span class="nav-text">简单回溯法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#使用限界函数"><span class="nav-number">2.2.</span> <span class="nav-text">使用限界函数</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#地图着色问题"><span class="nav-number">3.</span> <span class="nav-text">地图着色问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#马踏棋盘"><span class="nav-number">4.</span> <span class="nav-text">马踏棋盘</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#算24"><span class="nav-number">5.</span> <span class="nav-text">算24</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#算式拼凑"><span class="nav-number">6.</span> <span class="nav-text">算式拼凑</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#1-2-3-4-5-6-7-8-9-110"><span class="nav-number">6.1.</span> <span class="nav-text">1 2 3 4 5 6 7 8 9 &#x3D; 110</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#无优先级运算"><span class="nav-number">6.2.</span> <span class="nav-text">无优先级运算</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#全排列"><span class="nav-number">7.</span> <span class="nav-text">全排列</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#递归方法"><span class="nav-number">7.1.</span> <span class="nav-text">递归方法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#系统函数方法"><span class="nav-number">7.2.</span> <span class="nav-text">系统函数方法</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#八皇后"><span class="nav-number">8.</span> <span class="nav-text">八皇后</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#迷宫"><span class="nav-number">9.</span> <span class="nav-text">迷宫</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#八数码"><span class="nav-number">10.</span> <span class="nav-text">八数码</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#ROAD"><span class="nav-number">11.</span> <span class="nav-text">ROAD</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#作业调度问题"><span class="nav-number">12.</span> <span class="nav-text">作业调度问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#符号三角形"><span class="nav-number">13.</span> <span class="nav-text">符号三角形</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#最大团问题"><span class="nav-number">14.</span> <span class="nav-text">最大团问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#货郎问题"><span class="nav-number">15.</span> <span class="nav-text">货郎问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#圆排列问题"><span class="nav-number">16.</span> <span class="nav-text">圆排列问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#连续邮资问题"><span class="nav-number">17.</span> <span class="nav-text">连续邮资问题</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#回溯法"><span class="nav-number">17.1.</span> <span class="nav-text">回溯法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#回溯法-动态规划法"><span class="nav-number">17.2.</span> <span class="nav-text">回溯法+动态规划法</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">羊书change</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Muse</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/yangshucheng2020/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/yangshucheng2020/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/yangshucheng2020/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/yangshucheng2020/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/yangshucheng2020/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/yangshucheng2020/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/yangshucheng2020/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/yangshucheng2020/js/src/motion.js?v=5.1.4"></script>



  
  

  
  <script type="text/javascript" src="/yangshucheng2020/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/yangshucheng2020/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/yangshucheng2020/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
